// 前缀和 + 动态规划 + 哈希表
// 本质上是一个动态规划的思想，关键步骤如下：
// 1.确定状态表示
// 2.推导动态转移方程
// 3.初始化
// 4.确定填表顺序
// 5.确定返回值

// 例题 5：
// 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
// 子数组是数组中元素的连续非空序列。
//
//        示例 1：
//
//        输入：nums = [1,1,1], k = 2
//        输出：2
//        示例 2：
//
//        输入：nums = [1,2,3], k = 3
//        输出：2
//
//        提示：
//
//        1 <= nums.length <= 2 * 104
//        -1000 <= nums[i] <= 1000
//        -107 <= k <= 107

// 解题思路：
// 本题乍一看是一个找子数组个数的题目，首先就会想到用滑动窗口的办法
// 再仔细一看，发现数组里面的数值有正有负，数据本身不具备单调性，因此无法用滑动窗口解题
// 进而利用动态规划的思想进行解题，首先需要定义状态表示 dp[i]
// dp[i]：以 i 位置为结尾和为 k 的子数组的个数，定义完状态表示后，我们发现不好推导状态转移方程
// 原因是 dp[i] 和 dp[i - 1] 没有直接的关系，dp[i] 和前面的所有 dp[j] 有关系
// 因此想到使用前缀和的办法：dp[i] = 前缀和为 sum - k 的子数组的个数，这也同时符合“正难则反”的思想
// 统计个数最好的数据结构还是哈希表，因为哈希表查询的时间复杂度为 O(1)
// 因此，每动态规划一个 dp[i]，就需要把它相应的前缀和放进哈希表
// ret += dp[i]，即 ret += hash.getOrDefault(sum - k, 0);

import java.util.HashMap;
import java.util.Map;

public class SubarraySum {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> hash = new HashMap<>();
        hash.put(0, 1);
        int sum = 0;
        int ret = 0;
        for(int x : nums){
            sum += x;
            ret += hash.getOrDefault(sum - k, 0);
            hash.put(sum, hash.getOrDefault(sum, 0) + 1);
        }
        return ret;
    }
}
